home *** CD-ROM | disk | FTP | other *** search
/ Celestin Apprentice 2 / Apprentice-Release2.iso / Source Code / C / Libraries / Berkeley DB 1.6 / btree / bt_get.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-06-04  |  6.1 KB  |  223 lines  |  [TEXT/????]
  1. /*-
  2.  * Copyright (c) 1990, 1993
  3.  *    The Regents of the University of California.  All rights reserved.
  4.  *
  5.  * This code is derived from software contributed to Berkeley by
  6.  * Mike Olson.
  7.  *
  8.  * Redistribution and use in source and binary forms, with or without
  9.  * modification, are permitted provided that the following conditions
  10.  * are met:
  11.  * 1. Redistributions of source code must retain the above copyright
  12.  *    notice, this list of conditions and the following disclaimer.
  13.  * 2. Redistributions in binary form must reproduce the above copyright
  14.  *    notice, this list of conditions and the following disclaimer in the
  15.  *    documentation and/or other materials provided with the distribution.
  16.  * 3. All advertising materials mentioning features or use of this software
  17.  *    must display the following acknowledgement:
  18.  *    This product includes software developed by the University of
  19.  *    California, Berkeley and its contributors.
  20.  * 4. Neither the name of the University nor the names of its contributors
  21.  *    may be used to endorse or promote products derived from this software
  22.  *    without specific prior written permission.
  23.  *
  24.  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  25.  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  26.  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27.  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  28.  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  29.  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  30.  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  31.  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  32.  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  33.  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  34.  * SUCH DAMAGE.
  35.  */
  36.  
  37. #if defined(LIBC_SCCS) && !defined(lint)
  38. static char sccsid[] = "@(#)bt_get.c    8.1 (Berkeley) 6/4/93";
  39. #endif /* LIBC_SCCS and not lint */
  40.  
  41. #include <sys/types.h>
  42.  
  43. #include <errno.h>
  44. #include <stddef.h>
  45. #include <stdio.h>
  46.  
  47. #include <db.h>
  48. #include "btree.h"
  49.  
  50. /*
  51.  * __BT_GET -- Get a record from the btree.
  52.  *
  53.  * Parameters:
  54.  *    dbp:    pointer to access method
  55.  *    key:    key to find
  56.  *    data:    data to return
  57.  *    flag:    currently unused
  58.  *
  59.  * Returns:
  60.  *    RET_ERROR, RET_SUCCESS and RET_SPECIAL if the key not found.
  61.  */
  62. int
  63. __bt_get(dbp, key, data, flags)
  64.     const DB *dbp;
  65.     const DBT *key;
  66.     DBT *data;
  67.     u_int flags;
  68. {
  69.     BTREE *t;
  70.     EPG *e;
  71.     int exact, status;
  72.  
  73.     if (flags) {
  74.         errno = EINVAL;
  75.         return (RET_ERROR);
  76.     }
  77.     t = dbp->internal;
  78.     if ((e = __bt_search(t, key, &exact)) == NULL)
  79.         return (RET_ERROR);
  80.     if (!exact) {
  81.         mpool_put(t->bt_mp, e->page, 0);
  82.         return (RET_SPECIAL);
  83.     }
  84.  
  85.     /*
  86.      * A special case is if we found the record but it's flagged for
  87.      * deletion.  In this case, we want to find another record with the
  88.      * same key, if it exists.  Rather than look around the tree we call
  89.      * __bt_first and have it redo the search, as __bt_first will not
  90.      * return keys marked for deletion.  Slow, but should never happen.
  91.      */
  92.     if (ISSET(t, B_DELCRSR) && e->page->pgno == t->bt_bcursor.pgno &&
  93.         e->index == t->bt_bcursor.index) {
  94.         mpool_put(t->bt_mp, e->page, 0);
  95.         if ((e = __bt_first(t, key, &exact)) == NULL)
  96.             return (RET_ERROR);
  97.         if (!exact)
  98.             return (RET_SPECIAL);
  99.     }
  100.  
  101.     status = __bt_ret(t, e, NULL, data);
  102.     mpool_put(t->bt_mp, e->page, 0);
  103.     return (status);
  104. }
  105.  
  106. /*
  107.  * __BT_FIRST -- Find the first entry.
  108.  *
  109.  * Parameters:
  110.  *    t:    the tree
  111.  *    key:    the key
  112.  *
  113.  * Returns:
  114.  *    The first entry in the tree greater than or equal to key.
  115.  */
  116. EPG *
  117. __bt_first(t, key, exactp)
  118.     BTREE *t;
  119.     const DBT *key;
  120.     int *exactp;
  121. {
  122.     register PAGE *h;
  123.     register EPG *e;
  124.     EPG save;
  125.     pgno_t cpgno, pg;
  126.     indx_t cindex;
  127.     int found;
  128.  
  129.     /*
  130.      * Find any matching record; __bt_search pins the page.  Only exact
  131.      * matches are tricky, otherwise just return the location of the key
  132.      * if it were to be inserted into the tree.
  133.      */
  134.     if ((e = __bt_search(t, key, exactp)) == NULL)
  135.         return (NULL);
  136.     if (!*exactp)
  137.         return (e);
  138.  
  139.     if (ISSET(t, B_DELCRSR)) {
  140.         cpgno = t->bt_bcursor.pgno;
  141.         cindex = t->bt_bcursor.index;
  142.     } else {
  143.         cpgno = P_INVALID;
  144.         cindex = 0;        /* GCC thinks it's uninitialized. */
  145.     }
  146.  
  147.     /*
  148.      * Walk backwards, skipping empty pages, as long as the entry matches
  149.      * and there are keys left in the tree.  Save a copy of each match in
  150.      * case we go too far.  A special case is that we don't return a match
  151.      * on records that the cursor references that have already been flagged
  152.      * for deletion.
  153.      */
  154.     save = *e;
  155.     h = e->page;
  156.     found = 0;
  157.     do {
  158.         if (cpgno != h->pgno || cindex != e->index) {
  159.             if (save.page->pgno != e->page->pgno) {
  160.                 mpool_put(t->bt_mp, save.page, 0);
  161.                 save = *e;
  162.             } else
  163.                 save.index = e->index;
  164.             found = 1;
  165.         }
  166.         /*
  167.          * Make a special effort not to unpin the page the last (or
  168.          * original) match was on, but also make sure it's unpinned
  169.          * if an error occurs.
  170.          */
  171.         while (e->index == 0) {
  172.             if (h->prevpg == P_INVALID)
  173.                 goto done1;
  174.             if (h->pgno != save.page->pgno)
  175.                 mpool_put(t->bt_mp, h, 0);
  176.             if ((h = mpool_get(t->bt_mp, h->prevpg, 0)) == NULL) {
  177.                 if (h->pgno == save.page->pgno)
  178.                     mpool_put(t->bt_mp, save.page, 0);
  179.                 return (NULL);
  180.             }
  181.             e->page = h;
  182.             e->index = NEXTINDEX(h);
  183.         }
  184.         --e->index;
  185.     } while (__bt_cmp(t, key, e) == 0);
  186.  
  187.     /*
  188.      * Reach here with the last page that was looked at pinned, which may
  189.      * or may not be the same as the last (or original) match page.  If
  190.      * it's not useful, release it.
  191.      */
  192. done1:    if (h->pgno != save.page->pgno)
  193.         mpool_put(t->bt_mp, h, 0);
  194.  
  195.     /*
  196.      * If still haven't found a record, the only possibility left is the
  197.      * next one.  Move forward one slot, skipping empty pages and check.
  198.      */
  199.     if (!found) {
  200.         h = save.page;
  201.         if (++save.index == NEXTINDEX(h)) {
  202.             do {
  203.                 pg = h->nextpg;
  204.                 mpool_put(t->bt_mp, h, 0);
  205.                 if (pg == P_INVALID) {
  206.                     *exactp = 0;
  207.                     return (e);
  208.                 }
  209.                 if ((h = mpool_get(t->bt_mp, pg, 0)) == NULL)
  210.                     return (NULL);
  211.             } while ((save.index = NEXTINDEX(h)) == 0);
  212.             save.page = h;
  213.         }
  214.         if (__bt_cmp(t, key, &save) != 0) {
  215.             *exactp = 0;
  216.             return (e);
  217.         }
  218.     }
  219.     *e = save;
  220.     *exactp = 1;
  221.     return (e);
  222. }
  223.